Semana 1



In [1]:

    
def cria_matriz(tot_lin, tot_col, valor):
    matriz = []  #lista vazia
    for i in range(tot_lin):
        linha = []
        for j in range(tot_col):
            linha.append(valor)
        matriz.append(linha)
        return matriz



In [3]:

    
x = cria_matriz(2, 3, 99)
x









    Out[3]:





[[99, 99, 99]]



In [4]:

    
def cria_matriz(tot_lin, tot_col, valor):
    matriz = []  #lista vazia
    for i in range(tot_lin):
        linha = []
        for j in range(tot_col):
            linha.append(valor)
        matriz.append(linha)
    return matriz



In [5]:

    
x = cria_matriz(2, 3, 99)
x









    Out[5]:





[[99, 99, 99], [99, 99, 99]]

Este código faz com que primeiramente toda a primeira linha seja preenchida, em seguida a segunda e assim sucessivamente. Se nós quiséssemos que a primeira coluna fosse preenchida e em seguida a segunda coluna e assim por diante, como ficaria o código?

Um exemplo: se o usuário digitasse o seguinte comando “x = cria_matriz(2,3)” e em seguida informasse os seis números para serem armazenados na matriz, na seguinte ordem: 1, 2, 3, 4, 5, 6; o x teria ao final da função a seguinte matriz: [[1, 3, 5], [2, 4, 6]].



In [6]:

    
def cria_matriz(num_linhas, num_colunas):
    matriz = []  #lista vazia
    for i in range(num_linhas):
        linha = []
        for j in range(num_colunas):
            linha.append(0)
        matriz.append(linha)

    for i in range(num_colunas):
        for j in range(num_linhas):
            matriz[j][i] = int(input("Digite o elemento [" + str(j) + "][" + str(i) + "]: "))

    return matriz



In [7]:

    
x = cria_matriz(2, 3)









    



Digite o elemento [0][0]: 1
Digite o elemento [1][0]: 2
Digite o elemento [0][1]: 3
Digite o elemento [1][1]: 4
Digite o elemento [0][2]: 5
Digite o elemento [1][2]: 6



In [8]:

    
x









    Out[8]:





[[1, 3, 5], [2, 4, 6]]



In [10]:

    
def tarefa(mat):
    dim = len(mat)
    for i in range(dim):
        print(mat[i][dim-1-i], end="  ")

mat = [[1,2,3],[4,5,6],[7,8,9]]
tarefa(mat)

# Observação: o trecho do print (end = " ") irá mudar a finalização padrão do print
# que é pular para a próxima linha. Com esta mudança, o cursor permanecerá na mesma 
# linha aguardando a impressão seguinte.

Exercício 1: Tamanho da matriz

Escreva uma função dimensoes(matriz) que recebe uma matriz como parâmetro e imprime as dimensões da matriz recebida, no formato iXj.

Exemplos:

minha_matriz = [[1], [2], [3]]

dimensoes(minha_matriz)

3X1

minha_matriz = [[1, 2, 3], [4, 5, 6]]

dimensoes(minha_matriz)

2X3



In [1]:

    
def dimensoes(A):
    
    '''Função que recebe uma matriz como parâmetro e imprime as dimensões da matriz recebida, no formato iXj.
    
    Obs: i = colunas, j = linhas
    
    Exemplo: 
    >>> minha_matriz = [[1], 
                        [2], 
                        [3]
                        ]
    >>> dimensoes(minha_matriz)
    >>> 3X1
    '''
    
    lin = len(A)
    col = len(A[0])
    
    return print("%dX%d" % (lin, col))



In [2]:

    
matriz1 = [[1], [2], [3]]
dimensoes(matriz1)

3X1



In [3]:

    
matriz2 = [[1, 2, 3], [4, 5, 6]]
dimensoes(matriz2)

2X3

Exercício 2: Soma de matrizes

Escreva a função soma_matrizes(m1, m2) que recebe 2 matrizes e devolve uma matriz que represente sua soma caso as matrizes tenham dimensões iguais. Caso contrário, a função deve devolver False.

Exemplos:

m1 = [[1, 2, 3], [4, 5, 6]]

m2 = [[2, 3, 4], [5, 6, 7]]

soma_matrizes(m1, m2) => [[3, 5, 7], [9, 11, 13]]

m1 = [[1], [2], [3]]

m2 = [[2, 3, 4], [5, 6, 7]]

soma_matrizes(m1, m2) => False



In [7]:

    
def soma_matrizes(m1, m2):
    
    def dimensoes(A):
        lin = len(A)
        col = len(A[0])
    
        return ((lin, col))
    
    if dimensoes(m1) != dimensoes(m2):
        return False
    else:
        matriz = []
        for i in range(len(m1)):
            linha = []
            for j in range(len(m1[0])):
                linha.append(m1[i][j] + m2[i][j])
            matriz.append(linha)
        return matriz



In [8]:

    
m1 = [[1, 2, 3], [4, 5, 6]]
m2 = [[2, 3, 4], [5, 6, 7]]
soma_matrizes(m1, m2)









    Out[8]:





[[3, 5, 7], [9, 11, 13]]



In [9]:

    
m1 = [[1], [2], [3]]
m2 = [[2, 3, 4], [5, 6, 7]]
soma_matrizes(m1, m2)









    Out[9]:





False

Praticar tarefa de programação: Exercícios adicionais (opcionais)

Exercício 1: Imprimindo matrizes

Como proposto na primeira vídeo-aula da semana, escreva uma função imprime_matriz(matriz), que recebe uma matriz como parâmetro e imprime a matriz, linha por linha. Note que NÃO se deve imprimir espaços após o último elemento de cada linha!

Exemplos:

minha_matriz = [[1], [2], [3]]

imprime_matriz(minha_matriz)

minha_matriz = [[1, 2, 3], [4, 5, 6]]

imprime_matriz(minha_matriz)

1 2 3

4 5 6



In [26]:

    
def imprime_matriz(A):
    
    for i in range(len(A)):
        for j in range(len(A[i])):
            print(A[i][j])



In [27]:

    
minha_matriz = [[1], [2], [3]]
imprime_matriz(minha_matriz)



In [28]:

    
minha_matriz = [[1, 2, 3], [4, 5, 6]]
imprime_matriz(minha_matriz)

Exercício 2: Matrizes multiplicáveis

Duas matrizes são multiplicáveis se o número de colunas da primeira é igual ao número de linhas da segunda. Escreva a função sao_multiplicaveis(m1, m2) que recebe duas matrizes como parâmetro e devolve True se as matrizes forem multiplicavéis (na ordem dada) e False caso contrário.

Exemplos:

m1 = [[1, 2, 3], [4, 5, 6]]

m2 = [[2, 3, 4], [5, 6, 7]]

sao_multiplicaveis(m1, m2) => False

m1 = [[1], [2], [3]]

m2 = [[1, 2, 3]]

sao_multiplicaveis(m1, m2) => True



In [30]:

    
def sao_multiplicaveis(m1, m2):
    
    '''Recebe duas matrizes como parâmetros e devolve True se as matrizes forem multiplicáveis (número de colunas 
    da primeira é igual ao número de linhs da segunda). False se não forem
    '''
    
    if len(m1) == len(m2[0]):
        return True
    else:
        return False



In [31]:

    
m1 = [[1, 2, 3], [4, 5, 6]]
m2 = [[2, 3, 4], [5, 6, 7]]
sao_multiplicaveis(m1, m2)









    Out[31]:





False



In [32]:

    
m1 = [[1], [2], [3]]
m2 = [[1, 2, 3]]
sao_multiplicaveis(m1, m2)









    Out[32]:





True

Semana 2



In [1]:

    
"áurea gosta de coentro".capitalize()









    Out[1]:





'Áurea gosta de coentro'



In [2]:

    
"AQUI".capitalize()









    Out[2]:





'Aqui'



In [3]:

    
# função para remover espaços em branco

"   email@company.com    ".strip()









    Out[3]:





'email@company.com'



In [4]:

    
"o abecedário da Xuxa é didático".count("a")









    Out[4]:





3



In [5]:

    
"o abecedário da Xuxa é didático".count("á")









    Out[5]:





2



In [6]:

    
"o abecedário da Xuxa é didático".count("X")









    Out[6]:





1



In [7]:

    
"o abecedário da Xuxa é didático".count("x")









    Out[7]:





1



In [8]:

    
"o abecedário da Xuxa é didático".count("z")









    Out[8]:





0



In [9]:

    
"A vida como ela seje".replace("seje", "é")









    Out[9]:





'A vida como ela é'



In [11]:

    
"áurea gosta de coentro".capitalize().center(80) #80 caracteres de largura, no centro apareça este texto









    Out[11]:





'                             Áurea gosta de coentro                             '



In [12]:

    
texto = "Ao que se percebe, só há o agora"
texto









    Out[12]:





'Ao que se percebe, só há o agora'



In [13]:

    
texto.find("q")









    Out[13]:





3



In [14]:

    
texto.find('se')









    Out[14]:





7



In [16]:

    
texto[7] + texto[8]









    Out[16]:





'se'



In [17]:

    
texto.find('w')









    Out[17]:





-1



In [18]:

    
fruta = 'amora'



In [20]:

    
fruta[:4] # desde o começo até a posição TRÊS!









    Out[20]:





'amor'



In [23]:

    
fruta[1:] # desde a posição 1 (começa no zero) até o final









    Out[23]:





'mora'



In [24]:

    
fruta[2:4] # desde a posição 2 até a posição 3









    Out[24]:





'or'

Exercício

Escrever uma função que recebe uma lista de Strings contendo nomes de pessoas como parâmetro e devolve o nome mais curto. A função deve ignorar espaços antes e depois do nome e deve devolver o nome com a primeira letra maiúscula.



In [30]:

    
def mais_curto(lista_de_nomes):
    
    menor = lista_de_nomes[0] # considerando que o menor nome está no primeiro lugar
    
    for i in lista_de_nomes:
        if len(i) < len(menor):
            menor = i
    
    return menor.capitalize()



In [31]:

    
lista = ['carlos', 'césar', 'ana', 'vicente', 'maicon', 'washington']



In [32]:

    
mais_curto(lista)









    Out[32]:





'Ana'



In [33]:

    
ord('a')









    Out[33]:





97



In [34]:

    
ord('A')









    Out[34]:





65



In [35]:

    
ord('b')









    Out[35]:





98



In [39]:

    
ord('m')









    Out[39]:





109



In [40]:

    
ord('M')









    Out[40]:





77



In [26]:

    
ord('AA')









    



---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)
<ipython-input-26-ce393a8d8496> in <module>()
----> 1 ord('AA')

TypeError: ord() expected a character, but string of length 2 found



In [36]:

    
'maçã' > 'banana'









    Out[36]:





True



In [37]:

    
'Maçã' > 'banana'









    Out[37]:





False



In [41]:

    
'Maçã'.lower() > 'banana'.lower()









    Out[41]:





True



In [56]:

    
txt = 'José'
txt = txt.lower()
txt









    Out[56]:





'josé'



In [92]:

    
lista = ['ana', 'maria', 'José', 'Valdemar']
len(lista)









    Out[92]:





4



In [93]:

    
lista[3].lower()









    Out[93]:





'valdemar'



In [94]:

    
lista[2]









    Out[94]:





'José'



In [95]:

    
lista[2] = lista[2].lower()



In [96]:

    
lista









    Out[96]:





['ana', 'maria', 'josé', 'Valdemar']



In [98]:

    
for i in lista:
    print(i)









    



ana
maria
josé
Valdemar



In [105]:

    
lista[0][0]









    Out[105]:





'a'



In [ ]:

Exercício

Escreva uma função que recebe um array de strings como parâmetro e devolve o primeiro string na ordem lexicográfica, ignorando-se maiúsculas e minúsculas



In [106]:

    
def menor_string(array_string):
    
    for i in range(len(array_string)):
        array_string[i] = array_string[i].lower()
    
    menor = array_string[0] # considera o primeiro como o menor
    
    for i in array_string:
        if ord(i[0][0]) < ord(menor[0]):
            menor = i
    
    return menor



In [111]:

    
lista = ['maria', 'José', 'Valdemar']



In [112]:

    
menor_string(lista)









    Out[112]:





'josé'



In [114]:

    
# Código para inverter string e deixa maiúsculo

def fazAlgo(string):
    pos = len(string)-1
    string = string.upper()
    while pos >= 0:
        print(string[pos],end = "")
        pos = pos - 1

fazAlgo("paralelepipedo")









    



ODEPIPELELARAP



In [115]:

    
# Código que deixa maiúsculo as letras de ordem ímpar: 

def fazAlgo(string):
    pos = 0
    string1 = ""
    string = string.lower()
    stringMa = string.upper()
    while pos < len(string):
        if pos % 2 == 0:
            string1 = string1 + stringMa[pos]
        else:
            string1 = string1 + string[pos]
        pos = pos + 1
    return string1    

print(fazAlgo("paralelepipedo"))









    



PaRaLeLePiPeDo



In [118]:

    
# Código que tira os espaços em branco

def fazAlgo(string):
    pos = 0
    string1 = ""
    while pos < len(string):
        if string[pos] != " ":
            string1 = string1 + string[pos]
        pos = pos + 1
    return string1    

print(fazAlgo("ISTO É UM TESTE"))









    



ISTOÉUMTESTE



In [135]:

    
# e para retornar "Istoéumteste", ou seja, só deixar a primeira letra maiúscula...

def fazAlgo(string):
    pos = 0
    string1 = ""    
    while pos < len(string):
        if string[pos] != " ":
            string1 = string1 + string[pos]
        pos = pos + 1
        string1 = string1.capitalize()
    return string1



In [136]:

    
print(fazAlgo("ISTO É UM TESTE"))









    



Istoéumteste



In [1]:

    
x, y = 10, 20



In [2]:

    
x, y









    Out[2]:





(10, 20)



In [3]:

    
x









    Out[3]:





10



In [4]:

    
y









    Out[4]:





20



In [5]:

    
def peso_altura():

    return 77, 1.83



In [6]:

    
peso_altura()









    Out[6]:





(77, 1.83)



In [8]:

    
peso, altura = peso_altura()



In [9]:

    
peso









    Out[9]:





77



In [10]:

    
altura









    Out[10]:





1.83



In [ ]:

    
# Atribuição múltipla em C (vacas magras...)
'''
int a, b, temp

a = 10
b = 20

temp = a
a = b
b = temp
'''



In [14]:

    
a, b = 10, 20
a, b = b, a
a, b









    Out[14]:





(20, 10)



In [15]:

    
# Atribuição aumentada

x = 10

x = x + 10

x









    Out[15]:





20



In [17]:

    
x = 10

x += 10

x









    Out[17]:





20



In [19]:

    
x = 3

x *= 2

x









    Out[19]:





6



In [20]:

    
x = 2
x **= 10
x









    Out[20]:





1024



In [22]:

    
x = 100
x /= 3
x









    Out[22]:





33.333333333333336



In [23]:

    
def pagamento_semanal(valor_por_hora, num_horas = 40):
    return valor_por_hora * num_horas



In [24]:

    
pagamento_semanal(10)









    Out[24]:





400



In [26]:

    
pagamento_semanal(10, 20) # aceita, mesmo assim, o segundo parâmetro.









    Out[26]:





200



In [27]:

    
# Asserção de Invariantes

def pagamento_semanal(valor_por_hora, num_horas = 40):
    assert valor_por_hora >= 0 and num_horas > 0    
    return valor_por_hora * num_horas



In [28]:

    
pagamento_semanal(30, 10)









    Out[28]:





300



In [29]:

    
pagamento_semanal(10, -10)









    



---------------------------------------------------------------------------
AssertionError                            Traceback (most recent call last)
<ipython-input-29-d4888163423a> in <module>()
----> 1 pagamento_semanal(10, -10)

<ipython-input-27-f3cd269ee201> in pagamento_semanal(valor_por_hora, num_horas)
      2 
      3 def pagamento_semanal(valor_por_hora, num_horas = 40):
----> 4     assert valor_por_hora >= 0 and num_horas > 0
      5     return valor_por_hora * num_horas

AssertionError:



In [30]:

    
x, y = 10, 12
x, y = y, x
print("x = ",x,"e y = ",y)









    



x =  12 e y =  10



In [31]:

    
x = 10
x += 10
x /= 2
x //= 3
x %= 2
x *= 9
print(x)

9.0



In [32]:

    
def calculo(x, y = 10, z = 5):
    return x + y * z;

calculo(1, 2, 3)









    Out[32]:





7



In [34]:

    
calculo(1, 2) # 2 entra em y.









    Out[34]:





11



In [36]:

    
def calculo(x, y = 10, z = 5):
    return x + y * z;

print(calculo(1, 2, 3))



In [37]:

    
calculo()









    



---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)
<ipython-input-37-b3086c7998bf> in <module>()
----> 1 calculo()

TypeError: calculo() missing 1 required positional argument: 'x'



In [38]:

    
print(calculo( ,12, 10))









    



  File "<ipython-input-38-5107460fd864>", line 1
    print(calculo( ,12, 10))
                   ^
SyntaxError: invalid syntax



In [39]:

    
def horario_em_segundos(h, m, s):
    assert h >= 0 and m >= 0 and s >= 0
    return h * 3600 + m * 60 + s

print(horario_em_segundos (3,0,50))



In [40]:

    
print(horario_em_segundos(1,2,3))



In [41]:

    
print(horario_em_segundos (-1,20,30))









    



---------------------------------------------------------------------------
AssertionError                            Traceback (most recent call last)
<ipython-input-41-8038a74e5713> in <module>()
----> 1 print(horario_em_segundos (-1,20,30))

<ipython-input-39-bc871fb3a4ba> in horario_em_segundos(h, m, s)
      1 def horario_em_segundos(h, m, s):
----> 2     assert h >= 0 and m >= 0 and s >= 0
      3     return h * 3600 + m * 60 + s
      4 
      5 print(horario_em_segundos (3,0,50))

AssertionError:



In [1]:

    
# Módulos em Python

def fib(n): # escreve a série de Fibonacci até n
    a, b = 0, 1
    while b < n:
        print(b, end = ' ')
        a, b = b, a + b
    print()

def fib2(n):
    result = []
    a, b = 0, 1
    while b < n:
        result.append(b)
        a, b = b, a + b
    return result



In [ ]:

    
'''
E no shell do Python (chamado na pasta que contém o arquivo fibo.py)
>>> import fibo
>>> fibo.fib(100)
1 1 2 3 5 8 13 21 34 55 89 
>>> fibo.fib2(100)
[1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89]
>>> fibo.fib2(1000)
[1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987]
>>> meuFib = fibo.fib
>>> meuFib(20)
1 1 2 3 5 8 13 

'''

Incluindo

```print(__name__)```

na última linha de fibo.py, ao fazer a importação import fibo no shell do Python, imprime 'fibo', que é o nome do programa.

Ao incluir

if __name__ == "__main__": 
    import sys
    fib(int(sys.argv[1]))

podemos ver se está sendo executado como script (com o if do jeito que está) ou como módulo dentro de outro código (se o nome não for main, está sendo importado pra usar alguma função lá dentro).



In [1]:

    
def fazAlgo(string): # inverte a string e deixa as vogais maiúsculas
    pos = len(string)-1 # define a variável posição do array
    stringMi = string.lower() # aqui estão todas minúsculas
    string = string.upper() # aqui estão todas maiúsculas
    stringRe = "" # string de retorno
    
    while pos >= 0:
        if string[pos] == 'A' or string[pos] == 'E' or string[pos] == 'I' or string[pos] == 'O' or string[pos] == 'U':
            stringRe = stringRe + string[pos]
        else:
            stringRe = stringRe + stringMi[pos]
        pos = pos - 1
    return stringRe

if __name__ == "__main__":
    print(fazAlgo("teste"))
    print(fazAlgo("o ovo do avestruz"))
    print(fazAlgo("A CASA MUITO ENGRAÇADA"))
    print(fazAlgo("A TELEvisão queBROU"))
    print(fazAlgo("A Vaca Amarela"))









    



EtsEt
zUrtsEvA Od OvO O
AdAçArgnE OtIUm AsAc A
UOrbEUq OãsIvElEt A
AlErAmA AcAv A

Exercício 1: Letras maiúsculas

Escreva a função maiusculas(frase) que recebe uma frase (uma string) como parâmetro e devolve uma string com as letras maiúsculas que existem nesta frase, na ordem em que elas aparecem.

Para resolver este exercício, pode ser útil verificar uma tabela ASCII, que contém os valores de cada caractere. Ver http://equipe.nce.ufrj.br/adriano/c/apostila/tabascii.htm

Note que para simplificar a solução do exercício, as frases passadas para a sua função não possuirão caracteres que não estejam presentes na tabela ASCII apresentada, como ç, á, É, ã, etc.

Dica: Os valores apresentados na tabela são os mesmos devolvidos pela função ord apresentada nas aulas.

Exemplos:



In [ ]:

    
maiusculas('Programamos em python 2?')
# deve devolver 'P'

maiusculas('Programamos em Python 3.')
# deve devolver 'PP'

maiusculas('PrOgRaMaMoS em python!')
# deve devolver 'PORMMS'



In [34]:

    
def maiusculas(frase):
    
    listRe = [] # lista de retorno vazia
    stringRe = '' # string de retorno vazia
    
    for ch in frase:
        if ord(ch) >=65 and ord(ch) <= 91:
            listRe.append(ch)      
    
    # retornando a lista para string
    stringRe = ''.join(listRe)
    
    return stringRe



In [40]:

    
maiusculas('Programamos em python 2?')









    Out[40]:





'P'



In [41]:

    
maiusculas('Programamos em Python 3.')









    Out[41]:





'PP'



In [42]:

    
maiusculas('PrOgRaMaMoS em python!')









    Out[42]:





'PORMMS'



In [24]:

    
x = ord('A')
y = ord('a')
x, y









    Out[24]:





(65, 97)



In [21]:

    
ord('B')









    Out[21]:





66



In [14]:

    
ord('Z')









    Out[14]:





90

Exercício 2: Menor nome

Como pedido no primeiro vídeo desta semana, escreva uma função menor_nome(nomes) que recebe uma lista de strings com nome de pessoas como parâmetro e devolve o nome mais curto presente na lista.

A função deve ignorar espaços antes e depois do nome e deve devolver o menor nome presente na lista. Este nome deve ser devolvido com a primeira letra maiúscula e seus demais caracteres minúsculos, independente de como tenha sido apresentado na lista passada para a função.

Quando houver mais de um nome com o menor comprimento dentre os nomes na lista, a função deve devolver o primeiro nome com o menor comprimento presente na lista.

Exemplos:



In [ ]:

    
menor_nome(['maria', 'josé', 'PAULO', 'Catarina'])
# deve devolver 'José'

menor_nome(['maria', ' josé  ', '  PAULO', 'Catarina  '])
# deve devolver 'José'

menor_nome(['Bárbara', 'JOSÉ  ', 'Bill'])
# deve devolver José



In [81]:

    
def menor_nome(nomes):
    
    tamanho = len(nomes) # pega a quantidade de nomes na lista
    menor = '' # variável para escolher o menor nome
    lista_limpa = [] # lista de nomes sem os espaços em branco
    
    # ignora espaços em branco
    for str in nomes:
        lista_limpa.append(str.strip())
        
    # verifica o menor nome
    menor = lista_limpa[0] # considera o primeiro como menor
    for str in lista_limpa:
        if len(str) < len(menor): # não deixei <= senão pegará um segundo menor de mesmo tamanho
            menor = str
            
    return menor.capitalize() # deixa a primeira letra maiúscula



In [83]:

    
menor_nome(['maria', 'josé', 'PAULO', 'Catarina'])
# deve devolver 'José'









    



José



In [84]:

    
menor_nome(['maria', ' josé  ', '  PAULO', 'Catarina  '])
# deve devolver 'José'









    



José



In [85]:

    
menor_nome(['Bárbara', 'JOSÉ  ', 'Bill'])
# deve devolver José









    



José



In [88]:

    
menor_nome(['Bárbara', 'JOSÉ  ', 'Bill', '     aDa '])

Ada

Exercícios adicionais

Exercício 1: Contando vogais ou consoantes

Escreva a função conta_letras(frase, contar="vogais"), que recebe como primeiro parâmetro uma string contendo uma frase e como segundo parâmetro uma outra string. Este segundo parâmetro deve ser opcional.

Quando o segundo parâmetro for definido como "vogais", a função deve devolver o numero de vogais presentes na frase. Quando ele for definido como "consoantes", a função deve devolver o número de consoantes presentes na frase. Se este parâmetro não for passado para a função, deve-se assumir o valor "vogais" para o parâmetro.

Exemplos:

conta_letras('programamos em python')

conta_letras('programamos em python', 'vogais')

conta_letras('programamos em python', 'consoantes')



In [125]:

    
def conta_letras(frase, contar = 'vogais'):
    
    pos = len(frase) - 1 # atribui na variável pos (posição) a posição do array
    count = 0 # define o contador de vogais
    
    while pos >= 0: # conta as vogais
        if frase[pos] == 'a' or frase[pos] == 'e' or frase[pos] == 'i' or frase[pos] == 'o' or frase[pos] == 'u':
            count += 1
        pos = pos - 1
    
    if contar == 'consoantes':
        frase = frase.replace(' ', '')     # retira espaços em branco
        return len(frase) - count # subtrai do total as vogais
    else:
        return count



In [126]:

    
conta_letras('programamos em python')









    Out[126]:





6



In [127]:

    
conta_letras('programamos em python', 'vogais')









    Out[127]:





6



In [128]:

    
conta_letras('programamos em python', 'consoantes')









    Out[128]:





13



In [129]:

    
conta_letras('bcdfghjklmnpqrstvxywz', 'consoantes')









    Out[129]:





21



In [130]:

    
len('programamos em python')









    Out[130]:





21



In [131]:

    
frase = 'programamos em python'
frase.replace(' ', '')
frase









    Out[131]:





'programamos em python'

Exercício 2: Ordem lexicográfica

Como pedido no segundo vídeo da semana, escreva a função primeiro_lex(lista) que recebe uma lista de strings como parâmetro e devolve o primeiro string na ordem lexicográfica. Neste exercício, considere letras maiúsculas e minúsculas.

Dica: revise a segunda vídeo-aula desta semana.

Exemplos:

primeiro_lex(['oĺá', 'A', 'a', 'casa'])

'A'

primeiro_lex(['AAAAAA', 'b'])

'AAAAAA'



In [29]:

    
def primeiro_lex(lista):
    
    resposta = lista[0] # define o primeiro item da lista como a resposta...mas verifica depois.
    
    for str in lista:
        if ord(str[0]) < ord(resposta[0]):
            resposta = str
    
    return resposta



In [ ]:

    
assert primeiro_lex(['oĺá', 'A', 'a', 'casa']), 'A'



In [ ]:

    
assert primeiro_lex(['AAAAAA', 'b']), 'AAAAAA'



In [35]:

    
primeiro_lex(['casa', 'a', 'Z', 'A'])









    Out[35]:





'A'



In [133]:

    
primeiro_lex(['AAAAAA', 'b'])









    Out[133]:





'AAAAAA'

Semana 3 - POO – Programação Orientada a Objetos



In [142]:

    
def cria_matriz(tot_lin, tot_col, valor):

    matriz = []  #lista vazia

    for i in range(tot_lin):
        linha = []
        for j in range(tot_col):
            linha.append(valor)
        matriz.append(linha)
    
    return matriz



In [144]:

    
# import matriz # descomentar apenas no arquivo .py

def soma_matrizes(A, B):
    
    num_lin = len(A)
    num_col = len(A[0])
    
    C = cria_matriz(num_lin, num_col, 0) # matriz com zeros
    
    for lin in range(num_lin): # percorre as linhas da matriz
        for col in range(num_col): # percorre as colunas da matriz
            C[lin][col] = A[lin][col] + B[lin][col]
        
    return C

if __name__ == '__main__':
    A = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
    B = [[10, 20, 30], [40, 50, 60], [70, 80, 90]]
    print(soma_matrizes(A, B))









    



[[11, 22, 33], [44, 55, 66], [77, 88, 99]]



In [ ]:

    
# No arquivo matriz.py

def cria_matriz(tot_lin, tot_col, valor):

    matriz = []  #lista vazia

    for i in range(tot_lin):
        linha = []
        for j in range(tot_col):
            linha.append(valor)
        matriz.append(linha)
    
    return matriz

# E no arquivo soma_matrizes.py

import matriz

def soma_matrizes(A, B):
    
    num_lin = len(A)
    num_col = len(A[0])
    
    C = matriz.cria_matriz(num_lin, num_col, 0) # matriz com zeros
    
    for lin in range(num_lin): # percorre as linhas da matriz
        for col in range(num_col): # percorre as colunas da matriz
            C[lin][col] = A[lin][col] + B[lin][col]
        
    return C

if __name__ == '__main__':
    A = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
    B = [[10, 20, 30], [40, 50, 60], [70, 80, 90]]
    print(soma_matrizes(A, B))



In [ ]:

    
'''
Multiplicação de matrizes:

1 2 3      1 2     22 28
4 5 6   *  3 4  =  49 64
           5 6 
           
1*1 + 2*3 + 3*5 = 22
1*2 + 2*4 + 3*6 = 28
4*1 + 5*3 + 6*5 = 49    
4*2 + 5*4 + 6*6 = 64

c11 = a11*b11 + a12*b21 + c13*c31
c12 = a11*b21 + a12*b22 + c13*c23
c21 = a21*b11 + a22*b21 + c23*c31
c22 = a21*b21 + a22*b22 + c23*c23
'''



In [151]:

    
def multiplica_matrizes (A, B):
    
    num_linA, num_colA = len(A), len(A[0])
    num_linB, num_colB = len(B), len(B[0])
    
    assert num_colA == num_linB
    
    C = []
    
    for lin in range(num_linA): # percorre as linhas da matriz A
        # começando uma nova linha
        C.append([])
        for col in range(num_colB): # percorre as colunas da matriz B
            # Adicionando uma nova coluna na linha
            C[lin].append(0)
            for k in range(num_colA):
                C[lin][col] += A[lin][k] * B[k][col]     

    return C

if __name__ == '__main__':
    A = [[1, 2, 3], [4, 5, 6]]
    B = [[1, 2], [3, 4], [5, 6]]
    print(multiplica_matrizes(A, B))









    



[[22, 28], [49, 64]]

POO



In [153]:

    
class Carro:
    pass

meu_carro = Carro()
meu_carro









    Out[153]:





<__main__.Carro at 0x7f4f7898ffd0>



In [155]:

    
carro_do_trabalho = Carro()
carro_do_trabalho









    Out[155]:





<__main__.Carro at 0x7f4f789883c8>



In [156]:

    
meu_carro.ano = 1968
meu_carro.modelo = 'Fusca'
meu_carro.cor = 'azul'



In [157]:

    
meu_carro.ano









    Out[157]:





1968



In [158]:

    
meu_carro.cor









    Out[158]:





'azul'



In [159]:

    
carro_do_trabalho.ano = 1981
carro_do_trabalho.modelo = 'Brasília'
carro_do_trabalho.cor = 'amarela'



In [160]:

    
carro_do_trabalho.ano









    Out[160]:





1981



In [162]:

    
novo_fusca = meu_carro # duas variáveis apontando para o mesmo objeto



In [164]:

    
novo_fusca #repare que é o mesmo end. de memória









    Out[164]:





<__main__.Carro at 0x7f4f7898ffd0>



In [165]:

    
novo_fusca.ano += 10



In [166]:

    
novo_fusca.ano









    Out[166]:





1978



In [167]:

    
novo_fusca









    Out[167]:





<__main__.Carro at 0x7f4f7898ffd0>

Testes para praticar



In [168]:

    
class Pato:
  pass

pato = Pato()
patinho = Pato()
if pato == patinho:
  print("Estamos no mesmo endereço!")
else:
  print("Estamos em endereços diferentes!")









    



Estamos em endereços diferentes!



In [172]:

    
class Carro:
    def __init__(self, modelo, ano, cor): # init é o Construtor da classe
        self.modelo = modelo
        self.ano = ano
        self.cor = cor



In [173]:

    
carro_do_meu_avo = Carro('Ferrari', 1980, 'vermelha')
carro_do_meu_avo









    Out[173]:





<__main__.Carro at 0x7f4f7898a828>



In [174]:

    
carro_do_meu_avo.cor









    Out[174]:





'vermelha'

POO – Programação Orientada a Objetos – Parte 2



In [6]:

    
def main():
    carro1 = Carro('Brasília', 1968, 'amarela', 80)
    carro2 = Carro('Fuscão', 1981, 'preto', 95)
    
    carro1.acelere(40)
    carro2.acelere(50)
    carro1.acelere(80)
    carro1.pare()
    carro2.acelere(100)
    
class Carro:
    
    def __init__(self, modelo, ano, cor, vel_max):
        self.modelo = modelo
        self.ano    = ano
        self.cor    = cor
        self.vel    = 0
        self.maxV   = vel_max # velocidade máxima
    
    def imprima(self):
        if self.vel == 0: # parado dá para ver o ano
            print('%s %s %d' % (self.modelo, self.cor, self.ano))
        elif self.vel < self.maxV:
            print('%s %s indo a %d km/h' % (self.modelo, self.cor, self.vel))
        else:
            print('%s %s indo muito rapido!' % (self.modelo, self.cor))
    
    def acelere(self, velocidade):
        self.vel = velocidade
        if self.vel > self.maxV:
            self.vel = self.maxV
        self.imprima()
        
    def pare(self):
        self.vel = 0
        self.imprima()
    
main()









    



Brasília amarela indo a 40 km/h
Fuscão preto indo a 50 km/h
Brasília amarela indo muito rapido!
Brasília amarela 1968
Fuscão preto indo muito rapido!

TESTE PARA PRATICAR POO – Programação Orientada a Objetos – Parte 2



In [7]:

    
class Cafeteira:
  def __init__(self, marca, tipo, tamanho, cor):
    self.marca = marca
    self.tipo = tipo
    self.tamanho = tamanho
    self.cor = cor



In [15]:

    
class Cachorro:
  def __init__(self, raça, idade, nome, cor):
    self.raça = raça
    self.idade = idade
    self.nome = nome
    self.cor = cor
    
rex = Cachorro('vira-lata', 2, 'Bobby', 'marrom')



In [16]:

    
'vira-lata' == rex.raça









    Out[16]:





True



In [17]:

    
rex.idade > 2









    Out[17]:





False



In [18]:

    
rex.idade == '2'









    Out[18]:





False



In [19]:

    
rex.nome == 'rex'









    Out[19]:





False



In [20]:

    
Bobby.cor == 'marrom'









    



---------------------------------------------------------------------------
NameError                                 Traceback (most recent call last)
<ipython-input-20-60ecef47743f> in <module>()
----> 1 Bobby.cor == 'marrom'

NameError: name 'Bobby' is not defined



In [21]:

    
rex.cor == 'marrom'









    Out[21]:





True



In [22]:

    
class Lista:
  def append(self, elemento):
    return "Oops! Este objeto não é uma lista"
    
lista = []

a = Lista()
b = a.append(7)

lista.append(b)



In [23]:

    
a









    Out[23]:





<__main__.Lista at 0x7f88999f4eb8>



In [24]:

    
b









    Out[24]:





'Oops! Este objeto não é uma lista'



In [25]:

    
lista









    Out[25]:





['Oops! Este objeto não é uma lista']

Códigos Testáveis



In [34]:

    
import math

class Bhaskara:

    def delta(self, a, b, c):
        return b ** 2 - 4 * a * c

    def main(self):
        a_digitado = float(input("Digite o valor de a:"))
        b_digitado = float(input("Digite o valor de b:"))
        c_digitado = float(input("Digite o valor de c:"))
        print(self.calcula_raizes(a_digitado, b_digitado, c_digitado))

    def calcula_raizes(self, a, b, c):
        d = self.delta(self, a, b, c)
        if d == 0:
            raiz1 = (-b + math.sqrt(d)) / (2 * a)
            return 1, raiz1 # indica que tem uma raiz e o valor dela
        else:
            if d < 0:
                return 0
            else:
                raiz1 = (-b + math.sqrt(d)) / (2 * a)
                raiz2 = (-b - math.sqrt(d)) / (2 * a)
                return 2, raiz1, raiz2



In [35]:

    
main()









    



Digite o valor de a:10
Digite o valor de b:10
Digite o valor de c:10
0



In [36]:

    
main()









    



Digite o valor de a:10
Digite o valor de b:20
Digite o valor de c:10
(1, -1.0)



In [38]:

    
import Bhaskara

class TestBhaskara:

    def testa_uma_raiz(self):
        b = Bhaskara.Bhaskara()
        assert b.calcula_raizes(1, 0, 0) == (1, 0)

    def testa_duas_raizes(self):
        b = Bhaskara.Bhaskara()
        assert b.calcula_raizes(1, -5, 6) == (2, 3, 2)

    def testa_zero_raizes(self):
        b = Bhaskara.Bhaskara()
        assert b.calcula_raizes(10, 10, 10) == 0
        
    def testa_raiz_negativa(self):
        b = Bhaskara.Bhaskara()
        assert b.calcula_raizes(10, 20, 10) == (1, -1)

Fixture: valor fixo para um conjunto de testes

@pytest.fixture



In [42]:

    
# Nos estudos ficou pytest_bhaskara.py

import Bhaskara
import pytest

class TestBhaskara:

    @pytest.fixture
    def b(self):
        return Bhaskara.Bhaskara()
    
    def testa_uma_raiz(self, b):
        assert b.calcula_raizes(1, 0, 0) == (1, 0)

    def testa_duas_raizes(self, b):
        assert b.calcula_raizes(1, -5, 6) == (2, 3, 2)

    def testa_zero_raizes(self, b):
        assert b.calcula_raizes(10, 10, 10) == 0
        
    def testa_raiz_negativa(self, b):
        assert b.calcula_raizes(10, 20, 10) == (1, -1)









    



---------------------------------------------------------------------------
ImportError                               Traceback (most recent call last)
<ipython-input-42-b1f9ab1890f3> in <module>()
      1 import Bhaskara
----> 2 import pytest
      3 
      4 class TestBhaskara:
      5 

ImportError: No module named 'pytest'

Parametrização



In [44]:

    
def fatorial(n):
    if n < 0:
        return 0
    i = fat = 1
    while i <= n:
        fat = fat * i
        i += 1
    return fat

import pytest

@pytest.mark.parametrize("entrada, esperado", [
    (0, 1),
    (1, 1), 
    (-10, 0), 
    (4, 24),
    (5, 120)
    ])

def testa_fatorial(entrada, esperado):
    assert fatorial(entrada) == esperado









    



---------------------------------------------------------------------------
ImportError                               Traceback (most recent call last)
<ipython-input-44-0078dadb3bde> in <module>()
      8     return fat
      9 
---> 10 import pytest
     11 
     12 @pytest.mark.parametrize("entrada, esperado", [

ImportError: No module named 'pytest'

Exercícios

Escreva uma versão do TestaBhaskara usando @pytest.mark.parametrize
Escreva uma bateria de testes para o seu código preferido



In [ ]:



In [ ]:



In [ ]:



In [ ]:

Tarefa de programação: Lista de exercícios - 3

Exercício 1: Uma classe para triângulos

Defina a classe Triangulo cujo construtor recebe 3 valores inteiros correspondentes aos lados a, b e c de um triângulo.

A classe triângulo também deve possuir um método perimetro, que não recebe parâmetros e devolve um valor inteiro correspondente ao perímetro do triângulo.

t = Triangulo(1, 1, 1)

deve atribuir uma referência para um triângulo de lados 1, 1 e 1 à variável t

Um objeto desta classe deve responder às seguintes chamadas:

t.a

deve devolver o valor do lado a do triângulo

t. b

deve devolver o valor do lado b do triângulo

t.c

deve devolver o valor do lado c do triângulo

t.perimetro()

deve devolver um inteiro correspondente ao valor do perímetro do triângulo.



In [13]:

    
class Triangulo:
    
    def __init__(self, a, b, c):
        self.a = a
        self.b = b
        self.c = c
        
    def perimetro(self):
        return self.a + self.b + self.c



In [14]:

    
t = Triangulo(1, 1, 1)



In [15]:

    
t.a









    Out[15]:





1



In [16]:

    
t.b









    Out[16]:





1



In [17]:

    
t.c









    Out[17]:





1



In [18]:

    
t.perimetro()









    Out[18]:





3

Exercício 2: Tipos de triângulos

Na classe triângulo, definida na Questão 1, escreva o metodo tipo_lado() que devolve uma string dizendo se o triângulo é:

isóceles (dois lados iguais)

equilátero (todos os lados iguais)

escaleno (todos os lados diferentes)

Note que se o triângulo for equilátero, a função não deve devolver isóceles.

Exemplos:

t = Triangulo(4, 4, 4) t.tipo_lado()

deve devolver 'equilátero'

u = Triangulo(3, 4, 5) .tipo_lado()

deve devolver 'escaleno'



In [24]:

    
class Triangulo:
    
    def __init__(self, a, b, c):
        self.a = a
        self.b = b
        self.c = c
        
    def tipo_lado(self):
        if self.a == self.b and self.a == self.c:
            return 'equilátero'
        elif self.a != self.b and self.a != self.c and self.b != self.c:
            return 'escaleno'
        else:
            return 'isósceles'



In [25]:

    
t = Triangulo(4, 4, 4)
t.tipo_lado()









    Out[25]:





'equilátero'



In [26]:

    
u = Triangulo(3, 4, 5)
u.tipo_lado()









    Out[26]:





'escaleno'



In [27]:

    
v = Triangulo(1, 3, 3)
v.tipo_lado()









    Out[27]:





'isósceles'



In [28]:

    
t = Triangulo(5, 8, 5)
t.tipo_lado()









    Out[28]:





'isósceles'



In [29]:

    
t = Triangulo(5, 5, 6)
t.tipo_lado()









    Out[29]:





'isósceles'



In [30]:

    
'''
Exercício 1: Triângulos retângulos

Escreva, na classe Triangulo, o método retangulo() que devolve 
True se o triângulo for retângulo, e False caso contrário.

Exemplos:

t = Triangulo(1, 3, 5)
t.retangulo()
# deve devolver False

u = Triangulo(3, 4, 5)
u.retangulo()
# deve devolver True
'''









    Out[30]:





'\nExercício 1: Triângulos retângulos\n\nEscreva, na classe Triangulo, o método retangulo() que devolve True se o triângulo for retângulo, e False caso contrário.\n\nExemplos:\n\nt = Triangulo(1, 3, 5)\nt.retangulo()\n# deve devolver False\n\nu = Triangulo(3, 4, 5)\nu.retangulo()\n# deve devolver True\n'



In [36]:

    
class Triangulo:
    
    def __init__(self, a, b, c):
        self.a = a
        self.b = b
        self.c = c
        
    def retangulo(self):
        if self.a > self.b and self.a > self.c:
            if self.a ** 2 == self.b ** 2 + self.c ** 2:
                return True
            else:
                return False
        elif self.b > self.a and self.b > self.c:
            if self.b ** 2 == self.c ** 2 + self.a ** 2:
                return True
            else:
                return False
        else:
            if self.c ** 2 == self.a ** 2 + self.b ** 2:
                return True
            else:
                return False



In [37]:

    
t = Triangulo(1, 3, 5)
t.retangulo()









    Out[37]:





False



In [38]:

    
t = Triangulo(3, 1, 5)
t.retangulo()









    Out[38]:





False



In [39]:

    
t = Triangulo(5, 1, 3)
t.retangulo()









    Out[39]:





False



In [40]:

    
u = Triangulo(3, 4, 5)
u.retangulo()









    Out[40]:





True



In [41]:

    
u = Triangulo(4, 5, 3)
u.retangulo()









    Out[41]:





True



In [42]:

    
u = Triangulo(5, 3, 4)
u.retangulo()









    Out[42]:





True

Exercício 2: Triângulos semelhantes

Ainda na classe Triangulo, escreva um método semelhantes(triangulo) que recebe um objeto do tipo Triangulo como parâmetro e verifica se o triângulo atual é semelhante ao triângulo passado como parâmetro.

Caso positivo, o método deve devolver True. Caso negativo, deve devolver False.

Verifique a semelhança dos triângulos através do comprimento dos lados.

Dica: você pode colocar os lados de cada um dos triângulos em uma lista diferente e ordená-las.

Exemplo:

t1 = Triangulo(2, 2, 2)

t2 = Triangulo(4, 4, 4)

t1.semelhantes(t2)

deve devolver True

'''



In [23]:

    
class Triangulo:

    '''
    O resultado dos testes com seu programa foi:

    ***** [0.2 pontos]: Testando método semelhantes(Triangulo(3, 4, 5)) para Triangulo(3, 4, 5) - Falhou *****
    TypeError: 'Triangulo' object is not iterable

    ***** [0.2 pontos]: Testando método semelhantes(Triangulo(3, 4, 5)) para Triangulo(6, 8, 10) - Falhou *****
    TypeError: 'Triangulo' object is not iterable

    ***** [0.2 pontos]: Testando método semelhantes(Triangulo(6, 8, 10)) para Triangulo(3, 4, 5) - Falhou *****
    TypeError: 'Triangulo' object is not iterable

    ***** [0.4 pontos]: Testando método semelhantes(Triangulo(3, 3, 3)) para Triangulo(3, 4, 5) - Falhou *****
    TypeError: 'Triangulo' object is not iterable

    '''
    def __init__(self, a, b, c):
        self.a = a
        self.b = b
        self.c = c

# https://stackoverflow.com/questions/961048/get-class-that-defined-method
    def semelhantes(self, Triangulo):
        
        list1 = []
        
        for arg in self:
            list1.append(arg)
            
        list2 = []
        
        for arg in self1:
            list2.append(arg)
        
        
        for i in list2:
            print(i)



In [24]:

    
t1 = Triangulo(2, 2, 2)
t2 = Triangulo(4, 4, 4)
t1.semelhantes(t2)









    



---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)
<ipython-input-24-35450f00cdda> in <module>()
      1 t1 = Triangulo(2, 2, 2)
      2 t2 = Triangulo(4, 4, 4)
----> 3 t1.semelhantes(t2)

<ipython-input-23-70f97682acc0> in semelhantes(self, Triangulo)
     27         list1 = []
     28 
---> 29         for arg in self:
     30             list1.append(arg)
     31 

TypeError: 'Triangulo' object is not iterable

Week 4

Busca Sequencial



In [1]:

    
def busca_sequencial(seq, x):
    '''(list, bool) -> bool'''
    for i in range(len(seq)):
        if seq[i] == x:
            return True
    return False

# código com cara de C =\



In [4]:

    
list = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

busca_sequencial(list, 3)









    Out[4]:





True



In [6]:

    
list = ['casa', 'texto', 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

busca_sequencial(list, 'texto')









    Out[6]:





True



In [14]:

    
class Musica:
    
    def __init__(self, titulo, interprete, compositor, ano):
        self.titulo = titulo
        self.interprete = interprete
        self.compositor = compositor
        self.ano = ano

class Buscador:
    
    def busca_por_titulo(self, playlist, titulo):
        for i in range(len(playlist)):
            if playlist[i].titulo == titulo:
                return i
        return -1

    def vamos_buscar(self):
        playlist = [Musica("Ponta de Areia", "Milton Nascimento", "Milton Nascimento", 1975),
                    Musica("Podres Poderes", "Caetano Veloso", "Caetano Veloso", 1984), 
                    Musica("Baby", "Gal Costa", "Caetano Veloso", 1969)]
        
        onde_achou = self.busca_por_titulo(playlist, "Baby")
        
        if onde_achou == -1:
            print("A música buscada não está na playlist")
        else:
            preferida = playlist[onde_achou]
            print(preferida.titulo, preferida.interprete, preferida.compositor, preferida.ano, sep = ', ')



In [15]:

    
b = Buscador()



In [16]:

    
b.vamos_buscar()









    



Baby, Gal Costa, Caetano Veloso, 1969

Complexidade Computacional

Análise matemática do desempenho de um algoritmo
Estudo analítico de:
- Quantas operações um algoritmo requer para que ele seja executado
- Quanto tempo ele vai demorar para ser executado
- Quanto de memória ele vai ocupar

Análise da Busca Sequencial

Exemplo:

Lista telefônica de São Paulo, supondo 2 milhões de telefones fixos.

Supondo que cada iteração do for comparação de string dure 1 milissegundo.

Pior caso: 2000s = 33,3 minutos

Caso médio (1 milhão): 1000s = 16,6 minutos

Complexidade Computacional da Busca Sequencial

Dada uma lista de tamanho n
A complexidade computacional da busca sequencial é:
- n, no pior caso
- n/2, no caso médio

Conclusão

Busca sequencial é boa pois é bem simples
Funciona bem quando a busca é feita num volume pequeno de dados
Sua Complexidade Computacional é muito alta
É muito lenta quando o volume de dados é grande
Portanto, dizemos que é um algoritmo ineficiente

Algoritmo de Ordenação Seleção Direta

Seleção Direta

A cada passo, busca pelo menor elemento do pedaço ainda não ordenado da lista e o coloca no início da lista

No 1º passo, busca o menor elemento de todos e coloca na posição inicial da lista.

No 2º passo, busca o 2º menor elemento da lista e coloca na 2ª posição da lista.

No 3º passo, busca o 3º menor elemento da lista e coloca na 3ª posição da lista.

Repete até terminar a lista



In [17]:

    
class Ordenador:
    
    def selecao_direta(self, lista):
        
        fim = len(lista)
        
        for i in range(fim - 1):
            # Inicialmente o menor elemento já visto é o i-ésimo
            posicao_do_minimo = i
            
            for j in range(i + 1, fim):
                if lista[j] < lista[posicao_do_minimo]: # encontrou um elemento menor...
                    posicao_do_minimo = j               # ...substitui.
            
            # Coloca o menor elemento encontrado no início da sub-lista
            # Para isso, troca de lugar os elementos nas posições i e posicao_do_minimo
            
            lista[i], lista[posicao_do_minimo] = lista[posicao_do_minimo], lista[i]



In [18]:

    
lista = [10, 3, 8, -10, 200, 17, 32]
o = Ordenador()



In [20]:

    
o.selecao_direta(lista)



In [21]:

    
lista









    Out[21]:





[-10, 3, 8, 10, 17, 32, 200]



In [42]:

    
lista_nomes = ['maria', 'carlos', 'wilson', 'ana']
o.selecao_direta(lista_nomes)
lista_nomes









    Out[42]:





['ana', 'carlos', 'maria', 'wilson']



In [26]:

    
import random

print(random.randint(1, 10))



In [33]:

    
from random import shuffle
x = [i for i in range(100)]
shuffle(x)
x









    Out[33]:





[47,
 22,
 11,
 45,
 4,
 75,
 28,
 7,
 0,
 14,
 40,
 35,
 89,
 79,
 61,
 17,
 32,
 62,
 87,
 76,
 84,
 72,
 21,
 16,
 94,
 13,
 15,
 5,
 39,
 26,
 43,
 29,
 65,
 31,
 68,
 91,
 69,
 98,
 83,
 66,
 36,
 70,
 67,
 80,
 97,
 74,
 59,
 30,
 6,
 19,
 9,
 57,
 63,
 58,
 49,
 86,
 33,
 48,
 25,
 53,
 23,
 50,
 90,
 18,
 12,
 73,
 41,
 55,
 78,
 44,
 93,
 27,
 10,
 64,
 3,
 71,
 46,
 85,
 8,
 95,
 24,
 34,
 38,
 99,
 96,
 51,
 20,
 42,
 88,
 37,
 92,
 56,
 52,
 82,
 81,
 60,
 1,
 2,
 54,
 77]



In [35]:

    
o.selecao_direta(x)
x









    Out[35]:





[0,
 1,
 2,
 3,
 4,
 5,
 6,
 7,
 8,
 9,
 10,
 11,
 12,
 13,
 14,
 15,
 16,
 17,
 18,
 19,
 20,
 21,
 22,
 23,
 24,
 25,
 26,
 27,
 28,
 29,
 30,
 31,
 32,
 33,
 34,
 35,
 36,
 37,
 38,
 39,
 40,
 41,
 42,
 43,
 44,
 45,
 46,
 47,
 48,
 49,
 50,
 51,
 52,
 53,
 54,
 55,
 56,
 57,
 58,
 59,
 60,
 61,
 62,
 63,
 64,
 65,
 66,
 67,
 68,
 69,
 70,
 71,
 72,
 73,
 74,
 75,
 76,
 77,
 78,
 79,
 80,
 81,
 82,
 83,
 84,
 85,
 86,
 87,
 88,
 89,
 90,
 91,
 92,
 93,
 94,
 95,
 96,
 97,
 98,
 99]



In [46]:

    
def comprova_ordem(list):
    
    flag = True
    
    for i in range(len(list) - 1):
        if list[i] > list[i + 1]:
            flag = False
    
    return flag



In [47]:

    
comprova_ordem(x)









    Out[47]:





True



In [48]:

    
list = [1, 2, 3, 4, 5]
list2 = [1, 3, 2, 4, 5]

comprova_ordem(list)









    Out[48]:





True



In [49]:

    
comprova_ordem(list2)









    Out[49]:





False



In [40]:

    
def busca_sequencial(seq, x):
    for i in range(len(seq)):
        if seq[i] == x:
            return True
    return False



In [43]:

    
def selecao_direta(lista):
    fim = len(lista)
    for i in range(fim-1):
        pos_menor = i
        for j in range(i+1,fim):
            if lista[j] < lista[pos_menor]:
                pos_menor = j
        lista[i],lista[pos_menor] = lista[pos_menor],lista[i]
    return lista

numeros = [55,33,0,900,-432,10,77,2,11]

Tarefa de programação: Lista de exercícios - 4

Exercício 1: Lista ordenada

Escreva a função ordenada(lista), que recebe uma lista com números inteiros como parâmetro e devolve o booleano True se a lista estiver ordenada e False se a lista não estiver ordenada.



In [50]:

    
def ordenada(list):
    
    flag = True
    
    for i in range(len(list) - 1):
        if list[i] > list[i + 1]:
            flag = False
    
    return flag

Exercício 2: Busca sequencial

Implemente a função busca(lista, elemento), que busca um determinado elemento em uma lista e devolve o índice correspondente à posição do elemento encontrado. Utilize o algoritmo de busca sequencial. Nos casos em que o elemento buscado não existir na lista, a função deve devolver o booleano False.

busca(['a', 'e', 'i'], 'e')

deve devolver => 1

busca([12, 13, 14], 15)

deve devolver => False



In [54]:

    
def busca(lista, elemento):

    for i in range(len(lista)):
        if lista[i] == elemento:
            return i
    return False



In [55]:

    
busca(['a', 'e', 'i'], 'e')









    Out[55]:





1



In [56]:

    
busca([12, 13, 14], 15)









    Out[56]:





False

Praticar tarefa de programação: Exercícios adicionais (opcionais)

Exercício 1: Gerando listas grandes

Escreva a função lista_grande(n), que recebe como parâmetro um número inteiro n e devolve uma lista contendo n números inteiros aleatórios.



In [61]:

    
def lista_grande(n):
    
    import random
    return random.sample(range(1, 1000), n)



In [62]:

    
lista_grande(10)









    Out[62]:





[296, 119, 785, 433, 475, 88, 173, 495, 923, 486]



In [ ]:



In [ ]:



In [ ]:



In [ ]:

Exercício 2: Ordenação com selection sort

Implemente a função ordena(lista), que recebe uma lista com números inteiros como parâmetro e devolve esta lista ordenada. Utilize o algoritmo selection sort.



In [71]:

    
def ordena(lista):
    
    fim = len(lista)
    
    for i in range(fim - 1):
        min = i
        
        for j in range(i + 1, fim):
            if lista[j] < lista[min]:
                min = j
    
        lista[i], lista[min] = lista[min], lista[i]
    
    return lista



In [72]:

    
lista = [10, 3, 8, -10, 200, 17, 32]
ordena(lista)
lista









    Out[72]:





[-10, 3, 8, 10, 17, 32, 200]

Week 5 - Algoritmo de Ordenação da Bolha - Bubblesort

Lista como um tubo de ensaio vertical, os elementos mais leves sobem à superfície como uma bolha, os mais pesados afundam.

Percorre a lista múltiplas vezes; a cada passagem, compara todos os elementos adjacentes e troca de lugar os que estiverem fora de ordem



In [83]:

    
class Ordenador:
    
    def selecao_direta(self, lista):
        
        fim = len(lista)
        
        for i in range(fim - 1):
            # Inicialmente o menor elemento já visto é o i-ésimo
            posicao_do_minimo = i
            
            for j in range(i + 1, fim):
                if lista[j] < lista[posicao_do_minimo]: # encontrou um elemento menor...
                    posicao_do_minimo = j               # ...substitui.
            
            # Coloca o menor elemento encontrado no início da sub-lista
            # Para isso, troca de lugar os elementos nas posições i e posicao_do_minimo
            
            lista[i], lista[posicao_do_minimo] = lista[posicao_do_minimo], lista[i]
            
    def bolha(self, lista):
        
        fim = len(lista)
        
        for i in range(fim - 1, 0, -1):
            for j in range(i):
                if lista[j] > lista[j + 1]:
                    lista[j], lista[j + 1] = lista[j + 1], lista[j]

Exemplo do algoritmo bubblesort em ação:

Inicial: 5 1 7 3 2

1 5 7 3 2

1 5 3 7 2

1 5 3 2 7 (fim da primeira iteração)

1 3 5 2 7

1 3 2 5 7 (fim da segunda iteração)

1 2 3 5 7



In [84]:

    
lista = [10, 3, 8, -10, 200, 17, 32]

o = Ordenador()
o.bolha(lista)
lista









    Out[84]:





[-10, 3, 8, 10, 17, 32, 200]

Comparação de Desempenho

Módulo time:

função time()
devolve o tempo decorrido (em segundos) desde 1/1/1970 (no Unix)

Para medir um intervalo de tempo

import time

antes = time.time()

algoritmo_a_ser_cronometrado()

depois = time.time()

print("A execução do algoritmo demorou ", depois - antes, "segundos")



In [90]:

    
class Ordenador:
    
    def selecao_direta(self, lista):
        
        fim = len(lista)
        
        for i in range(fim - 1):
            # Inicialmente o menor elemento já visto é o i-ésimo
            posicao_do_minimo = i
            
            for j in range(i + 1, fim):
                if lista[j] < lista[posicao_do_minimo]: # encontrou um elemento menor...
                    posicao_do_minimo = j               # ...substitui.
            
            # Coloca o menor elemento encontrado no início da sub-lista
            # Para isso, troca de lugar os elementos nas posições i e posicao_do_minimo
            
            lista[i], lista[posicao_do_minimo] = lista[posicao_do_minimo], lista[i]
            
    def bolha(self, lista):
        
        fim = len(lista)
        
        for i in range(fim - 1, 0, -1):
            for j in range(i):
                if lista[j] > lista[j + 1]:
                    lista[j], lista[j + 1] = lista[j + 1], lista[j] 

import random
import time

class ContaTempos:
    
    def lista_aleatoria(self, n): # n = número de elementos da lista
        from random import randrange
        lista = [0 for x in range(n)] # lista com n elementos, todos sendo zero
        for i in range(n):
            lista[i] = random.randrange(1000) # inteiros entre 0 e 999
        return lista
        
    def compara(self, n):
        
        lista1 = self.lista_aleatoria(n)
        lista2 = lista1
        
        o = Ordenador()
        
        antes = time.time()
        o.bolha(lista1)
        depois = time.time()
        print("Bolha demorou", depois - antes, "segundos")
        
        antes = time.time()
        o.selecao_direta(lista2)
        depois = time.time()
        print("Seleção direta demorou", depois - antes, "segundos")



In [91]:

    
c = ContaTempos()
c.compara(1000)









    



Bolha demorou 0.16308164596557617 segundos
Seleção direta demorou 0.05245494842529297 segundos



In [93]:

    
print("Diferença de", 0.16308164596557617 - 0.05245494842529297)









    



Diferença de 0.1106266975402832



In [94]:

    
c.compara(5000)









    



Bolha demorou 2.776320695877075 segundos
Seleção direta demorou 1.2121152877807617 segundos

Melhoria no Algoritmo de Ordenação da Bolha

Percorre a lista múltiplas vezes; a cada passagem, compara todos os elementos adjacentes e troca de lugar os que estiverem fora de ordem.

Melhoria: se em uma das iterações, nenhuma troca é realizada, isso significa que a lista já está ordenada e podemos finalizar o algoritmo.



In [97]:

    
class Ordenador:
    
    def selecao_direta(self, lista):
        
        fim = len(lista)
        
        for i in range(fim - 1):
            # Inicialmente o menor elemento já visto é o i-ésimo
            posicao_do_minimo = i
            
            for j in range(i + 1, fim):
                if lista[j] < lista[posicao_do_minimo]: # encontrou um elemento menor...
                    posicao_do_minimo = j               # ...substitui.
            
            # Coloca o menor elemento encontrado no início da sub-lista
            # Para isso, troca de lugar os elementos nas posições i e posicao_do_minimo
            
            lista[i], lista[posicao_do_minimo] = lista[posicao_do_minimo], lista[i]
            
    def bolha(self, lista):
        
        fim = len(lista)
        
        for i in range(fim - 1, 0, -1):
            for j in range(i):
                if lista[j] > lista[j + 1]:
                    lista[j], lista[j + 1] = lista[j + 1], lista[j] 
    
    def bolha_curta(self, lista):
        
        fim = len(lista)
        
        for i in range(fim - 1, 0, -1):
            trocou = False
            for j in range(i):
                if lista[j] > lista[j + 1]:
                    lista[j], lista[j + 1] = lista[j + 1], lista[j] 
                    trocou = True
            if not trocou: # que é igual a if trocou == False
                return 

import random
import time

class ContaTempos:
    
    def lista_aleatoria(self, n): # n = número de elementos da lista
        from random import randrange
        lista = [random.randrange(1000) for x in range(n)] # lista com n elementos, todos sendo aleatórios de 0 a 999
        return lista
    
    def lista_quase_ordenada(self, n):
        lista = [x for x in range(n)] # lista ordenada
        lista[n//10] = -500 # localizou o -500 no primeiro décimo da lista
        return lista        
        
    def compara(self, n):
        
        lista1 = self.lista_aleatoria(n)
        lista2 = lista1
        lista3 = lista2
        
        o = Ordenador()
        
        print("Comparando lista aleatórias")
        
        antes = time.time()
        o.bolha(lista1)
        depois = time.time()
        print("Bolha demorou", depois - antes, "segundos")
        
        antes = time.time()
        o.selecao_direta(lista2)
        depois = time.time()
        print("Seleção direta demorou", depois - antes, "segundos")
        
        antes = time.time()
        o.bolha_curta(lista3)
        depois = time.time()
        print("Bolha otimizada", depois - antes, "segundos")

        print("\nComparando lista quase ordenadas")
        
        lista1 = self.lista_quase_ordenada(n)
        lista2 = lista1
        lista3 = lista2
        
        antes = time.time()
        o.bolha(lista1)
        depois = time.time()
        print("Bolha demorou", depois - antes, "segundos")
        
        antes = time.time()
        o.selecao_direta(lista2)
        depois = time.time()
        print("Seleção direta demorou", depois - antes, "segundos")
        
        antes = time.time()
        o.bolha_curta(lista3)
        depois = time.time()
        print("Bolha otimizada", depois - antes, "segundos")



In [98]:

    
c = ContaTempos()
c.compara(1000)









    



Comparando lista aleatórias
Bolha demorou 0.14641308784484863 segundos
Seleção direta demorou 0.0519869327545166 segundos
Bolha otimizada 0.00013399124145507812 segundos

Comparando lista quase ordenadas
Bolha demorou 0.061202287673950195 segundos
Seleção direta demorou 0.054038286209106445 segundos
Bolha otimizada 0.0001220703125 segundos



In [99]:

    
c.compara(5000)









    



Comparando lista aleatórias
Bolha demorou 2.8065667152404785 segundos
Seleção direta demorou 1.2187814712524414 segundos
Bolha otimizada 0.0006206035614013672 segundos

Comparando lista quase ordenadas
Bolha demorou 1.4341330528259277 segundos
Seleção direta demorou 1.2611918449401855 segundos
Bolha otimizada 0.0005714893341064453 segundos

Site com algoritmos de ordenação http://nicholasandre.com.br/sorting/

Testes automatizados dos algoritmos de ordenação



In [102]:

    
class Ordenador:
    
    def selecao_direta(self, lista):
        
        fim = len(lista)
        
        for i in range(fim - 1):
            posicao_do_minimo = i
            
            for j in range(i + 1, fim):
                if lista[j] < lista[posicao_do_minimo]: 
                    posicao_do_minimo = j            
            lista[i], lista[posicao_do_minimo] = lista[posicao_do_minimo], lista[i]
            
    def bolha(self, lista):
        
        fim = len(lista)
        
        for i in range(fim - 1, 0, -1):
            for j in range(i):
                if lista[j] > lista[j + 1]:
                    lista[j], lista[j + 1] = lista[j + 1], lista[j] 
    
    def bolha_curta(self, lista):
        
        fim = len(lista)
        
        for i in range(fim - 1, 0, -1):
            trocou = False
            for j in range(i):
                if lista[j] > lista[j + 1]:
                    lista[j], lista[j + 1] = lista[j + 1], lista[j] 
                    trocou = True
            if not trocou:
                return 

import random
import time

class ContaTempos:
    
    def lista_aleatoria(self, n): 
        from random import randrange
        lista = [random.randrange(1000) for x in range(n)] 
        return lista
    
    def lista_quase_ordenada(self, n):
        lista = [x for x in range(n)] 
        lista[n//10] = -500 
        return lista        
    
import pytest

class TestaOrdenador:
    
    @pytest.fixture
    def o(self):
        return Ordenador()
    
    @pytest.fixture
    def l_quase(self):
        c = ContaTempos()
        return c.lista_quase_ordenada(100)
    
    @pytest.fixture
    def l_aleatoria(self):
        c = ContaTempos()
        return c.lista_aleatoria(100)
    
    def esta_ordenada(self, l):
        for i in range(len(l) - 1):
            if l[i] > l[i+1]:
                return False
        return True                
            
    def test_bolha_curta_aleatoria(self, o, l_aleatoria):
        o.bolha_curta(l_aleatoria)
        assert self.esta_ordenada(l_aleatoria)

    def test_selecao_direta_aleatoria(self, o, l_aleatoria):
        o.selecao_direta(l_aleatoria)
        assert self.esta_ordenada(l_aleatoria)   
    
    def test_bolha_curta_quase(self, o, l_quase):
        o.bolha_curta(l_quase)
        assert self.esta_ordenada(l_quase)

    def test_selecao_direta_quase(self, o, l_quase):
        o.selecao_direta(l_quase)
        assert self.esta_ordenada(l_quase)









    



---------------------------------------------------------------------------
ImportError                               Traceback (most recent call last)
<ipython-input-102-24021a6037eb> in <module>()
     50         return lista
     51 
---> 52 import pytest
     53 
     54 class TestaOrdenador:

ImportError: No module named 'pytest'



In [ ]:

    
[5, 2, 1, 3, 4]

2 5 1 3 4
2 1 5 3 4
2 1 3 5 4
2 1 3 4 5



In [ ]:

    
[2, 3, 4, 5, 1]

2 3 4 1 5
2 3 1 4 5
2 1 3 4 5
1 2 3 4 5

Busca Binária

Objetivo: localizar o elemento x em uma lista

Considere o elemento m do meio da lista
- se x == m ==> encontrou!
- se x < m ==> procure apenas na 1ª metade (da esquerda)
- se x > m ==> procure apenas na 2ª metade (da direita),
- repetir o processo até que o x seja encontrado ou que a sub-lista em questão esteja vazia



In [103]:

    
class Buscador:
    
    def busca_por_titulo(self, playlist, titulo):
        for i in range(len(playlist)):
            if playlist[i].titulo == titulo:
                return i
        return -1
    
    def busca_binaria(self, lista, x):
        primeiro = 0
        ultimo = len(lista) - 1
        
        while primeiro <= ultimo:
            meio = (primeiro + ultimo) // 2
            if lista[meio] == x:
                return meio
            else:
                if x < lista[meio]: # busca na primeira metade da lista
                    ultimo = meio - 1 # já foi visto que não está no elemento meio, então vai um a menos
                else: 
                    primeiro = meio + 1
        return -1



In [107]:

    
lista = [-100, 0, 20, 30, 50, 100, 3000, 5000]
b = Buscador()
b.busca_binaria(lista, 30)









    Out[107]:





3

Complexidade da Busca Binária

Dado uma lista de n elementos

No pior caso, teremos que efetuar: $$log_2n$$ comparações

No exemplo da lista telefônica (com 2 milhões de números): $$log_2(2 milhões) = 20,9$$ Portanto: resposta em menos de 21 milissegundos!

Conclusão

Busca Binária é um algoritmo bastante eficiente
Ao estudar a eficiência de um algoritmo é interessante:
- Analisar a complexidade computacional
- Realizar experimentos medindo o desempenho

Tarefa de programação: Lista de exercícios - 5

Exercício 1: Busca binária

Implemente a função busca(lista, elemento), que busca um determinado elemento em uma lista e devolve o índice correspondente à posição do elemento encontrado. Utilize o algoritmo de busca binária. Nos casos em que o elemento buscado não existir na lista, a função deve devolver o booleano False.

Além de devolver o índice correspondente à posição do elemento encontrado, sua função deve imprimir cada um dos índices testados pelo algoritmo.

Exemplo:

busca(['a', 'e', 'i'], 'e')

deve devolver => 1

busca([1, 2, 3, 4, 5], 6)

deve devolver => False

busca([1, 2, 3, 4, 5, 6], 4)

deve devolver => 3



In [14]:

    
def busca(lista, elemento):
    
    primeiro = 0
    ultimo = len(lista) - 1

    while primeiro <= ultimo:
        meio = (primeiro + ultimo) // 2
        if lista[meio] == elemento:
            print(meio)
            return meio
        else:
            if elemento < lista[meio]: # busca na primeira metade da lista
                ultimo = meio - 1 # já foi visto que não está no elemento meio, então vai um a menos
                print(meio) # função deve imprimir cada um dos índices testados pelo algoritmo.
            else: 
                primeiro = meio + 1
                print(meio)
    return False



In [15]:

    
busca(['a', 'e', 'i'], 'e')



In [16]:

    
busca([1, 2, 3, 4, 5], 6)









    



2
3
4






    Out[16]:





False



In [17]:

    
busca([1, 2, 3, 4, 5, 6], 4)



In [ ]:



In [ ]:

Exercício 2: Ordenação com bubble sort

Implemente a função bubble_sort(lista), que recebe uma lista com números inteiros como parâmetro e devolve esta lista ordenada. Utilize o algoritmo bubble sort.

Além de devolver uma lista ordenada, sua função deve imprimir os resultados parciais da ordenação ao fim de cada iteração do algoritmo ao longo da lista. Observe que, como a última iteração do algoritmo apenas verifica que a lista está ordenada, o último resultado deve ser impresso duas vezes. Portanto, se seu algoritmo precisa de duas passagens para ordenar a lista, e uma terceira para verificar que a lista está ordenada, 3 resultados parciais devem ser impressos.

bubble_sort([5, 1, 4, 2, 8])

[1, 4, 2, 5, 8]

[1, 2, 4, 5, 8]

deve devolver [1, 2, 4, 5, 8]



In [55]:

    
def bubble_sort(lista):
    
    fim = len(lista)

    for i in range(fim - 1, 0, -1):
        for j in range(i):
            if lista[j] > lista[j + 1]:
                lista[j], lista[j + 1] = lista[j + 1], lista[j]
        print(lista)
    print(lista)
    
    return lista



In [56]:

    
bubble_sort([5, 1, 4, 2, 8])

#[1, 4, 2, 5, 8]
#[1, 2, 4, 5, 8]
#[1, 2, 4, 5, 8]
#deve devolver [1, 2, 4, 5, 8]









    



[1, 4, 2, 5, 8]
[1, 2, 4, 5, 8]
[1, 2, 4, 5, 8]
[1, 2, 4, 5, 8]
[1, 2, 4, 5, 8]






    Out[56]:





[1, 2, 4, 5, 8]



In [57]:

    
bubble_sort([1, 3, 4, 2, 0, 5])

#Esperado:

#[1, 3, 2, 0, 4, 5]
#[1, 2, 0, 3, 4, 5]
#[1, 0, 2, 3, 4, 5]
#[0, 1, 2, 3, 4, 5]
#[0, 1, 2, 3, 4, 5]









    



[1, 3, 2, 0, 4, 5]
[1, 2, 0, 3, 4, 5]
[1, 0, 2, 3, 4, 5]
[0, 1, 2, 3, 4, 5]
[0, 1, 2, 3, 4, 5]
[0, 1, 2, 3, 4, 5]






    Out[57]:





[0, 1, 2, 3, 4, 5]



In [51]:

    
#O resultado dos testes com seu programa foi:

#***** [0.6 pontos]: Verificando funcionamento do bubble sort - Falhou *****
#AssertionError: Expected 
#[1, 3, 4, 2, 0, 5]
#[1, 3, 2, 0, 4, 5]
#[1, 2, 0, 3, 4, 5]
#[1, 0, 2, 3, 4, 5]
#[0, 1, 2, 3, 4, 5]
#[0, 1, 2, 3, 4, 5]

# but got 
#[1, 3, 4, 2, 0, 5]
#[1, 3, 2, 0, 4, 5]
#[1, 2, 0, 3, 4, 5]
#[1, 0, 2, 3, 4, 5]
#[0, 1, 2, 3, 4, 5]

Praticar tarefa de programação: Exercício adicional (opcional)

Exercício 1: Ordenação com insertion sort

Implemente a função insertion_sort(lista), que recebe uma lista com números inteiros como parâmetro e devolve esta lista ordenada. Utilize o algoritmo insertion sort.



In [62]:

    
def insertion_sort(lista):

    fim = len(lista)

    for i in range(fim - 1):
        posicao_do_minimo = i

        for j in range(i + 1, fim):
            if lista[j] < lista[posicao_do_minimo]: 
                posicao_do_minimo = j            
        lista[i], lista[posicao_do_minimo] = lista[posicao_do_minimo], lista[i]
    
    return lista

Week 6

Recursão (Definição. Como resolver um problema recursivo. Exemplos. Implementações.)



In [69]:

    
def fatorial(n):
    if n <= 1:                      # base da recursão
        return 1
    else:
        return n * fatorial(n - 1)  # chamada recursiva

import pytest

@pytest.mark.parametrize("entrada, esperado", [
    (0, 1),
    (1, 1), 
    (2, 2), 
    (3, 6),
    (4, 24), 
    (5, 120)    
])

def testa_fatorial(entrada, esperado):
    assert fatorial(entrada) == esperado









    



---------------------------------------------------------------------------
ImportError                               Traceback (most recent call last)
<ipython-input-69-f68d21c73334> in <module>()
      5         return n * fatorial(n - 1)  # chamada recursiva
      6 
----> 7 import pytest
      8 
      9 @pytest.mark.parametrize("entrada, esperado", [

ImportError: No module named 'pytest'



In [66]:

    
#fatorial.py

def fatorial(n):
    if n <= 1:                      # base da recursão
        return 1
    else:
        return n * fatorial(n - 1)  # chamada recursiva

import pytest

@pytest.mark.parametrize("entrada, esperado", [
    (0, 1),
    (1, 1), 
    (2, 2), 
    (3, 6),
    (4, 24), 
    (5, 120)    
])

def testa_fatorial(entrada, esperado):
    assert fatorial(entrada) == esperado









    



  File "<ipython-input-66-3075d2cf7465>", line 13
    asssert fatorial(entrada) == esperado
                   ^
SyntaxError: invalid syntax



In [71]:

    
# fibonacci.py

# Fn = 0 if n = 0
# Fn = 1 if n = 1
# Fn+1 + Fn-2 if n > 1

def fibonacci(n):
    if n < 2: 
        return n
    else:
        return fibonacci(n - 1) + fibonacci(n - 2)

import pytest

@pytest.mark.parametrize("entrada, esperado", [
    (0, 0),
    (1, 1), 
    (2, 1), 
    (3, 2),
    (4, 3), 
    (5, 5),
    (6, 8),
    (7, 13)
])

def testa_fibonacci(entrada, esperado):
    assert fibonacci(entrada) == esperado









    



---------------------------------------------------------------------------
ImportError                               Traceback (most recent call last)
<ipython-input-71-1244e42fe53f> in <module>()
     11         return fibonacci(n - 1) + fibonacci(n - 2)
     12 
---> 13 import pytest
     14 
     15 @pytest.mark.parametrize("entrada, esperado", [

ImportError: No module named 'pytest'



In [72]:

    
# busca binária

def busca_binaria(lista, elemento, min = 0, max = None):
    
    if max == None:             # se nada for passado, o tamanho máximo é  o tamanho da lista
        max = len(lista) - 1
    
    if max < min: # situação que não encontrou o elemento
        return False
    else:
        meio = min + (max - min) // 2
    
    if lista[meio] > elemento:
        return busca_binaria(lista, elemento, min, meio - 1)
    
    elif lista[meio] < elemento:
        return busca_binaria(lista, elemento, meio + 1, max)
    
    else:
        return meio



In [75]:

    
a = [10, 20, 30, 40, 50, 60]

import pytest

@pytest.mark.parametrize("lista, valor, esperado", [
    (a, 10, 0),
    (a, 20, 1),
    (a, 30, 2),
    (a, 40, 3),
    (a, 50, 4),
    (a, 60, 5),
    (a, 70, False),
    (a, 70, False),
    (a, 15, False),
    (a, -10, False)
])

def testa_busca_binaria(lista, valor, esperado):
    assert busca_binaria(lista, valor) == esperado









    



---------------------------------------------------------------------------
NameError                                 Traceback (most recent call last)
<ipython-input-75-51b460d6fcae> in <module>()
      1 a = [10, 20, 30, 40, 50, 60]
      2 
----> 3 @pytest.mark.parametrize("lista, valor, esperado", [
      4     (a, 10, 0),
      5     (a, 20, 1),

NameError: name 'pytest' is not defined

Mergesort

Ordenação por Intercalação:

Divida a lista na metade recursivamente, até que cada sublista contenha apenas 1 elemento (portanto, já ordenada).
Repetidamente, intercale as sublistas para produzir novas listas ordenadas.
Repita até que tenhamos apenas 1 lista no final (que estará ordenada).

Ex:

6 5 3 1 8 7 2 4

5 6 1 3 7 8 2 4

1 3 5 6 2 4 7 8

1 2 3 4 5 6 7 8



In [76]:

    
def merge_sort(lista):
    if len(lista) <= 1:
        return lista
    
    meio = len(lista) // 2
    
    lado_esquerdo = merge_sort(lista[:meio])
    lado_direito = merge_sort(lista[meio:])
    
    return merge(lado_esquerdo, lado_direito) # intercala os dois lados

def merge(lado_esquerdo, lado_direito):
    if not lado_esquerdo: # se o lado esquerdo for uma lista vazia...
        return lado_direito
    
    if not lado_direito: # se o lado direito for uma lista vazia...
        return lado_esquerdo
    
    if lado_esquerdo[0] < lado_direito[0]: # compara o primeiro elemento da posição do lado esquerdo com o primeiro do lado direito
        return [lado_esquerdo[0]] + merge(lado_esquerdo[1:], lado_direito) # merge(lado_esquerdo[1:]) ==> pega o lado esquerdo, menos o primeiro elemento
    
    return [lado_direito[0]] + merge(lado_esquerdo, lado_direito[1:])

Base da recursão é a condição que faz o problema ser definitivamente resolvido. Caso essa condição, essa base da recursão, não seja satisfeita, o problema continua sendo reduzido em instâncias menores até que a condição passe a ser satisfeita.

Chamada recursiva é a linha onde a função faz uma chamada a ela mesma.

Função recursiva é a função que chama ela mesma.

A linha 2 tem a condição que é a base da recursão

A linha 5 tem a chamada recursiva

Para o algoritmo funcionar corretamente, é necessário trocar a linha 3 por “return 1”

if (n < 2):

if (n <= 1):

No e no
looping infinito

Resultado: 6. Chamadas recursivas: nenhuma.

Resultado: 20. Chamadas recursivas: 24



In [116]:

    
def x(n):
    if n == 0:
        #<espaço A>
        print(n)
    else:
        #<espaço B>
        x(n-1)
        print(n)
        #<espaço C>
    #<espaço D>
#<espaço E>



In [117]:

    
x(10)



In [126]:

    
def x(n):
    if n >= 0 or n <= 2:
        print(n)
        # return n
    else:
        print(n-1)
        print(n-2)
        print(n-3)
        #return x(n-1) + x(n-2) + x(n-3)



In [127]:

    
print(x(6))









    



6
None



In [138]:

    
def busca_binaria(lista, elemento, min=0, max=None):
    if max == None:
        max = len(lista)-1

    if max < min:
        return False
    else:
        meio = min + (max-min)//2
        print(lista[meio])
    
    if lista[meio] > elemento:
        return busca_binaria(lista, elemento, min, meio - 1)
    elif lista[meio] < elemento:
        return busca_binaria(lista, elemento, meio + 1, max)
    else:
        return meio



In [139]:

    
a = [-10, -2, 0, 5, 66, 77, 99, 102, 239, 567, 875, 934]



In [140]:

    
a









    Out[140]:





[-10, -2, 0, 5, 66, 77, 99, 102, 239, 567, 875, 934]



In [141]:

    
busca_binaria(a, 99)

Tarefa de programação: Lista de exercícios - 6

Exercício 1: Soma dos elementos de uma lista

Implemente a função soma_lista(lista), que recebe como parâmetro uma lista de números inteiros e devolve um número inteiro correspondente à soma dos elementos desta lista.

Sua solução deve ser implementada utilizando recursão.



In [178]:

    
def soma_lista_tradicional_way(lista):
    
    soma = 0
    
    for i in range(len(lista)):
        soma += lista[i]
    
    return soma



In [179]:

    
a = [-10, -2, 0, 5, 66, 77, 99, 102, 239, 567, 875, 934]
soma_lista_tradicional_way(a)









    Out[179]:





2952



In [181]:

    
b = [-10, -2, 0, 5]
soma_lista_tradicional_way(b)









    Out[181]:





-7



In [199]:

    
def soma_lista(lista):
   
    if len(lista) == 1:
        return lista[0]
    else:
        return lista[0] + soma_lista(lista[1:])



In [200]:

    
a = [-10, -2, 0, 5, 66, 77, 99, 102, 239, 567, 875, 934]
soma_lista(a) # retorna 2952









    Out[200]:





2952



In [201]:

    
b = [-10, -2, 0, 5]
soma_lista(b)









    Out[201]:





-7

Exercício 2: Encontrando ímpares em uma lista

Implemente a função encontra_impares(lista), que recebe como parâmetro uma lista de números inteiros e devolve uma outra lista apenas com os números ímpares da lista dada.

Sua solução deve ser implementada utilizando recursão.

Dica: você vai precisar do método extend() que as listas possuem.



In [57]:

    
def encontra_impares_tradicional_way(lista):
    
    lista_impares = []
    
    for i in lista:
        if i % 2 != 0: # é impar!
            lista_impares.append(i)

    return lista_impares



In [58]:

    
a = [5, 66, 77, 99, 102, 239, 567, 875, 934]
encontra_impares_tradicional_way(a)









    Out[58]:





[5, 77, 99, 239, 567, 875]



In [59]:

    
b = [2, 5, 34, 66, 100, 102, 999]
encontra_impares_tradicional_way(b)









    Out[59]:





[5, 999]



In [2]:

    
stack = ['a','b']
stack.extend(['g','h'])
stack









    Out[2]:





['a', 'b', 'g', 'h']



In [ ]:



In [ ]:



In [1]:

    
def encontra_impares(lista):
    
    if len(lista) == 0:
        return []
    if lista[0] % 2 != 0: # se o elemento é impar
        return [lista[0]] + encontra_impares(lista[1:])
    else:
        return encontra_impares(lista[1:])



In [2]:

    
a = [5, 66, 77, 99, 102, 239, 567, 875, 934]
encontra_impares(a)









    Out[2]:





[5, 77, 99, 239, 567, 875]



In [4]:

    
encontra_impares([5])









    Out[4]:





[5]



In [5]:

    
encontra_impares([1, 2, 3])









    Out[5]:





[1, 3]



In [6]:

    
encontra_impares([2, 4, 6, 8])









    Out[6]:





[]



In [7]:

    
encontra_impares([9])









    Out[7]:





[9]



In [8]:

    
encontra_impares([4, 11])









    Out[8]:





[11]



In [9]:

    
encontra_impares([2, 10, 20, 7, 30, 12, 6, 6])









    Out[9]:





[7]



In [10]:

    
encontra_impares([])









    Out[10]:





[]



In [11]:

    
encontra_impares([4, 331, 1001, 4])









    Out[11]:





[331, 1001]

Exercício 3: Elefantes

Este exercício tem duas partes:

Implemente a função incomodam(n) que devolve uma string contendo "incomodam " (a palavra seguida de um espaço) n vezes. Se n não for um inteiro estritamente positivo, a função deve devolver uma string vazia. Essa função deve ser implementada utilizando recursão. Utilizando a função acima, implemente a função elefantes(n) que devolve uma string contendo a letra de "Um elefante incomoda muita gente..." de 1 até n elefantes. Se n não for maior que 1, a função deve devolver uma string vazia. Essa função também deve ser implementada utilizando recursão. Observe que, para um elefante, você deve escrever por extenso e no singular ("Um elefante..."); para os demais, utilize números e o plural ("2 elefantes...").

Dica: lembre-se que é possível juntar strings com o operador "+". Lembre-se também que é possível transformar números em strings com a função str().

Dica: Será que neste caso a base da recursão é diferente de n==1?

Por exemplo, uma chamada a elefantes(4) deve devolver uma string contendo:

Um elefante incomoda muita gente

2 elefantes incomodam incomodam muito mais

2 elefantes incomodam incomodam muita gente

3 elefantes incomodam incomodam incomodam muito mais

3 elefantes incomodam incomodam incomodam muita gente

4 elefantes incomodam incomodam incomodam incomodam muito mais



In [19]:

    
def incomodam(n):
    
    if type(n) != int or n <= 0:
        return ''
    else:
        s1 = 'incomodam '
        return s1 + incomodam(n - 1)



In [20]:

    
incomodam('-1')









    Out[20]:





''



In [21]:

    
incomodam(2)









    Out[21]:





'incomodam incomodam '



In [22]:

    
incomodam(3)









    Out[22]:





'incomodam incomodam incomodam '



In [23]:

    
incomodam(8)









    Out[23]:





'incomodam incomodam incomodam incomodam incomodam incomodam incomodam incomodam '



In [24]:

    
incomodam(-3)









    Out[24]:





''



In [25]:

    
incomodam(1)









    Out[25]:





'incomodam '



In [26]:

    
incomodam(7)









    Out[26]:





'incomodam incomodam incomodam incomodam incomodam incomodam incomodam '



In [140]:

    
def incomodam(n):
    
    if type(n) != int or n <= 0:
        return ''
    else:
        s1 = 'incomodam '
        return s1 + incomodam(n - 1)

def elefantes(n):
    
    if type(n) != int or n <= 0:
        return ''
    if n == 1:
        return "Um elefante incomoda muita gente"
    else:
        return elefantes(n - 1) + str(n) + " elefantes " + incomodam(n) + ("muita gente" if n % 2 > 0 else "muito mais") +  "\r\n"



In [141]:

    
elefantes(1)









    Out[141]:





'Um elefante incomoda muita gente'



In [142]:

    
print(elefantes(3))









    



Um elefante incomoda muita gente2 elefantes incomodam incomodam muito mais
3 elefantes incomodam incomodam incomodam muita gente



In [143]:

    
elefantes(2)









    Out[143]:





'Um elefante incomoda muita gente2 elefantes incomodam incomodam muito mais\r\n'



In [144]:

    
elefantes(3)









    Out[144]:





'Um elefante incomoda muita gente2 elefantes incomodam incomodam muito mais\r\n3 elefantes incomodam incomodam incomodam muita gente\r\n'



In [145]:

    
print(elefantes(4))









    



Um elefante incomoda muita gente2 elefantes incomodam incomodam muito mais
3 elefantes incomodam incomodam incomodam muita gente
4 elefantes incomodam incomodam incomodam incomodam muito mais



In [ ]:



In [ ]:



In [ ]:



In [24]:

    
type(str(3))









    Out[24]:





str



In [ ]:



In [4]:

    
def incomodam(n):
    
    if type(n) != int or n < 0:
        return ''
    else:
        return print('incomodam ' * n)
    
def elefantes(n):
    
    texto_inicial = 'Um elefante incomoda muita gente\n'
    texto_posterior1 = '%d elefantes ' + incomodam(n) + 'muito mais\n\n'
    texto_posterior2 = 'elefantes ' + incomodam(n) + 'muita gente\n'
    
    if n == 1:
        return print(texto_inicial)
    else:
        return print(texto_inicial) + print(texto_posterior1)



In [5]:

    
elefantes(1)









    



incomodam 






    



---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)
<ipython-input-5-5ee39444f63e> in <module>()
----> 1 elefantes(1)

<ipython-input-4-64930ad1be30> in elefantes(n)
      9 
     10     texto_inicial = 'Um elefante incomoda muita gente\n'
---> 11     texto_posterior1 = 'elefantes ' + incomodam(n) + 'muito mais\n\n'
     12     texto_posterior2 = 'elefantes ' + incomodam(n) + 'muita gente\n'
     13 

TypeError: Can't convert 'NoneType' object to str implicitly



In [3]:

    
elefantes(2)









    



incomodam incomodam 






    



---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)
<ipython-input-3-ec0c3762e019> in <module>()
----> 1 elefantes(2)

<ipython-input-1-bf7f88a3197f> in elefantes(n)
      9 
     10     texto_inicial = 'Um elefante incomoda muita gente\n'
---> 11     texto_posterior1 = 'elefantes ' + incomodam(n) + 'muito mais\n\n'
     12     texto_posterior2 = 'elefantes ' + incomodam(n) + 'muita gente\n'
     13 

TypeError: Can't convert 'NoneType' object to str implicitly

Praticar tarefa de programação: Exercícios adicionais (opcionais)

Exercício 1: Fibonacci

Implemente a função fibonacci(n), que recebe como parâmetro um número inteiro e devolve um número inteiro correspondente ao n-ésimo elemento da sequência de Fibonacci. Sua solução deve ser implementada utilizando recursão.

Exemplo:

fibonacci(4)

deve devolver => 3

fibonacci(2)

deve devolver => 1



In [ ]:



In [ ]:



In [ ]:



In [ ]:



In [ ]:



In [ ]:



In [ ]:

Exercício 2: Fatorial

Implemente a função fatorial(x), que recebe como parâmetro um número inteiro e devolve um número inteiro correspondente ao fatorial de x.

Sua solução deve ser implementada utilizando recursão.



In [ ]:



In [ ]: